package com.ctl.algorithm;

/**
 * <p>Title: SlidingWindow</p>
 * <p>Description: </p>
 * <p>Copyright: Copyright (c) 2019</p>
 * <p>Company: www.ctl.com</p>
 *给你两个长度相同的字符串，s和t。将s中的第i个字符变到t中的第i个字符需要|s[i]-t[i]|的开销（开销可能为0），
 * 也就是两个字符的ASCII码值的差的绝对值。用于变更字符串的最大预算是maxCost。
 * 在转化字符串时，总开销应当小于等于该预算，这也意味着字符串的转化可能是不完全的。
 * 如果你可以将s的子字符串转化为它在t中对应的子字符串，则返回可以转化的最大长度。
 * 如果s中没有子字符串可以转化成t中对应的子字符串，则返回0
 * @author ctl
 * @version 1.1
 * @date 2023-02-10 09:19
 */
public class SlidingWindow {
    public static int equalSubstring(String s, String t, int maxCost) {
        int length = s.length();
        int maxLen = 0;
        int left = 0;// 窗口左边界
        int right = 0;// 窗口右边界
        int cost = 0;// 字符串转换的开销
        while (right < length) {
            // 累加绝对值
            cost += Math.abs(s.charAt(right) - t.charAt(right));
            // 窗口中的元素开销太大，不满足条件，缩小窗口
            while (cost > maxCost) {
                cost -= Math.abs(s.charAt(left) - t.charAt(left));
                left++;// 缩小窗口
            }
            // 记录窗口最大值
            maxLen = Math.max(maxLen, right - left + 1);
            right++;// // 窗口右指针往右移
        }
        return maxLen;
    }
    public static int equalSubstringSelf(String s, String t, int maxCost) {
        int maxLength = 0;
        int length = s.length();
        int cost = 0;
        for (int i = 0; i < length; i++) {
            for (int j = i; j < length; j++) {
//                System.out.println("i=" + i + "\tj=" + j);
                cost += Math.abs(s.charAt(j) - t.charAt(j));
                if (cost > maxCost) {
                    cost = 0;
                    break;
                }
                maxLength = Math.max(maxLength, j - i + 1);
//               System.out.println("subStr="+s.substring(i,j+1));
            }
        }
        return maxLength;
    }
    public static void main(String[] args) {
        String s = "abcdaaaa", t = "bcdfaaaa";
        int maxCost = 3;
        System.out.println(equalSubstring(s, t, maxCost));
        System.out.println(equalSubstringSelf(s, t, maxCost));
    }
}
